### 找零兑换:动态规划解法

❖ 动态规划算法采用了一种更有条理的方式来得到问题的解。  
❖ 找零兑换的动态规划算法从最简单的1分钱找零”的最优解开始，逐步递加上去 ，直到我们需要的找零钱数。  
❖ 在找零递加的过程中，设法保持每一分钱的递加都是最优解，一直加到求解找零钱数，自然得到最优解。  
❖ 递加的过程能保持最优解的关键是，其依赖于更少钱数最优解的简单计算，而更少钱数的最优解已经得到了。  
❖ 问题的最优解包含了更小规模子问题的最优解，这是一个最优化问题能够用动态规划策略解决的必要条件。

- python 版

```python
def dpMakeChange(coinValueList,change,minCoins):
    # 从1分开始到change 逐个计算最少硬币数
    for cents in range(1,change+1):
        #1.初始化一个最大值
        coinCount = cents
        #2.减去每个硬币，向后查最少硬币数，同时记录总的最少数
        for j in [c for c in coinValueList if c <= cents]:
            coinCount= minCoins[cents - j ] + 1
        # 得到当前最少硬币数，记录到表中
        minCoins[cents] = coinCount
    return minCoins[change]

print(dpMakeChange([1,5,10,21,25],63,[0]*64))

```

### 找零兑换:动态规划算法扩展

❖ 我们注意到动态规划算法的 dpMakeChange 并不是递归函数,虽然这个问题是从递归算法开始解决，但最终我们得到一个更有条理的高效非递归算法。  
❖ 动态规划中最主要的思想是: 从最简单情况开始到达所需找零的循环其每一步都依靠以前的最优解来得到本步骤的最优解，直到得到答案。  
❖ 前面的算法已经得到了最少硬币的数量，但没有返回硬币如何组合。  
❖ 扩展算法的思路很简单，只需要在生成最优解列表同时跟踪记录所选择的那个硬币币值即可。  
❖ 在得到最后的解后，减去选择的硬币币值 ，回溯到表格之前的部分找零，就能逐步得到每一步所选择的硬币币值。

- python 版

```python
def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
    for cents in range(change+1):
        coinCount = cents
        newCoin = 1 # 初始化一下新加硬币
        for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents - j ] + 1 < coinCount:
                coinCount= minCoins[cents - j ] + 1
                newCoin = j # 对应最小数量，所减的硬币
        # 得到当前最少硬币数，记录到表中
        minCoins[cents] = coinCount
        coinsUsed[cents] = newCoin # 记录本步聚加的1个硬币
    return minCoins[change]

def printCoins(coinsUsed,change):
    coin = change
    while coin > 0:
        thisCoin = coinsUsed[coin]
        print(thisCoin)
        coin=coin=thisCoin

amnt = 63
clist = [1,5,10,21,25]
coinsUsed = [0] * (amnt + 1)
coinCount = [0] * (amnt + 1)
print('Making change for', amnt, 'requires')
print(dpMakeChange(clist,amnt,coinCount,coinsUsed),"coins")
print("Thev are")
```

### 讨论:博物馆大盗问题

大盗潜入博物馆，面前有5件宝物，分别有重量和价值，大盗的背包仅能负重 20 公斤，请问如何选择宝物，总价值最高?

| item | weight | value |
| :--: | :----: |:----: |
|1 | 2| 3|
|2|3|4|
|3|4|8|
|4|5|8|
|5|9|10|

- python 版

```python
# 宝物的重量和价值
tr = [None, {'w':2,"v":3},{'w':3,"v":4},{'w':4,"v":8},{'w':5,"v":8},{'w':9,"v":10}]
# 大盗最大承重
max_w = 20

# 初始化二维表格mr[(i,w)]
# 表示前i个宝物中，最大重量w的组合，所得到的最大价值
# 当i什么都不取，或W上限为e，价值均为0
m = {(i,w):0 for i in range(len(tr))
                for w in range(max_w +1)
     }

# 逐个填写二维表格
for i in range(1, len(tr)):
    for w in range(1, max_w + 1):
        if tr[i]['w'] > w: # 装不下第i个宝物
            m[(i,w)] = m[(i-1,w)] # 不装第i个宝物
        else:
            # 不装第i个宝物，装第i个宝物，两种情况下最大价值
            m[(i,w)] = max(
                m[(i-1),w],
                m[(i-1,w-tr[i]['w'])] + tr[i]['v']
            )

print(m[(len(tr) -1, max_w)])


# 宝物的重量和价值
tr = {(2,3),(3,4),(4,8),(5,8),(9,10)}
# 大盗最大承重
max_w = 20
# 初始化记忆化表格m
# key是(宝物组合，最大重量），value是最大价值
m = {}

def thief(tr,w):
    if tr == set() or w ==0:
        m[(tuple(tr),w)] = 0 # tuple 是key的要求
        return 0
    elif (tuple(tr),w) in m:
        return m[(tuple(tr), w)]
    else:
        vmax = 0
        for t in tr:
            if t[0] <= w:
                # 逐个从集合中去掉某个宝物，递归调用
                # 选出所有价值中的最大值
                v = thief(tr-{t}, w-t[0]+t[1])
                vmax = max(vmax,v)
        m[(tuple(tr), w)] = vmax
        return vmax
print(thief(tr,max_w))

```